package week8.jsjf;

import org.jetbrains.annotations.NotNull;
import week4.jsjf.ArrayUnorderedList;
import week6.jsjf.BinaryTreeADT;
import week7.jsjf.exceptions.ElementNotFoundException;
import week7.jsjf.exceptions.EmptyCollectionException;

import java.util.*;

/**
 * ArrayBinaryTree implements the BinaryTreeADT interface using an array
 *
 * @author Lewis and Chase
 * @version 4.0
 */
public class ArrayBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T>
{
    private static final int DEFAULT_CAPACITY = 50;
	
    protected int count;
    protected T[] tree; 
	protected int modCount;
//创建空的二叉树
    public ArrayBinaryTree() 
    {
        count = 0;
        tree = (T[]) new Object[DEFAULT_CAPACITY];
    }

   // 创建以指定元素为根的转换二叉树。
    public ArrayBinaryTree(T element) 
    {
        count = 1;
        tree = (T[]) new Object[DEFAULT_CAPACITY];
        tree[0] = element;
    }

    //私有方法扩大容量如果容量满了
    protected void expandCapacity()
    {
		tree = Arrays.copyOf(tree, tree.length * 2);   
    }
    
   //返回树的根节点
    @Override
    public T getRootElement() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayBinaryTree");

        return tree[0];
    }

    //返回真如果树为空
    @Override
    public boolean isEmpty()
    {
        return (count == 0);
    }

    //返回树的元素个数的整数型
    @Override
    public int size()
    {
        return count;
    }
    //如果该树包含一个元素，则返回true指定目标元素，否则为false。
    @Override
    public boolean contains(T targetElement)
    {
        T temp;
        boolean found = false;
        
        try 
        {
            temp = find(targetElement);
            found = true;
        }
        catch (Exception ElementNotFoundException) 
        {
            found = false;
        }
        
        return found;
    }

    //返回引用如果指定元素在二叉树中被找到  抛出 Translation ElementNotFoundException 如果指定元素没有在二叉树中被找到

    public T find(T targetElement) throws ElementNotFoundException
    {
        T temp = null;
        boolean found = false;
        
        for (int i = 0; i < tree.length && !found; i++)
            if (tree[i] != null)
                if (targetElement.equals(tree[i]))
                {
	                found = true;
                    temp = tree[i];
                }

        if (!found)
            throw new ElementNotFoundException("ArrayBinaryTree");

        return temp;
    }


    //层序遍历输出二叉树
    @Override
    public String toString()
    {
        ArrayList<T> tempList = new ArrayList<T>();
        levelOrder(0, tempList);

        return tempList.toString();
    }

    //返回迭代用中缀迭代器的方法
    @Override
    @NotNull
    public Iterator<T> iterator()
    {
        return this.iteratorInOrder();
    }
    

    @Override
    public Iterator<T> iteratorInOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        inOrder(0, tempList);

        return new TreeIterator(tempList.iterator());
    }


    protected void inOrder(int node, ArrayUnorderedList<T> tempList) 
    {
        if (node < tree.length)
            if (tree[node] != null)
            {
                inOrder(node * 2 + 1, tempList);
                tempList.addToRear(tree[node]);
                inOrder((node + 1) * 2, tempList);
            }
    }
    public void levelOrder(int root, ArrayList<T> temp)
    {
        int temp1=root;
        while(tree[temp1]!=null){
            temp.add(tree[temp1]);
                    temp1++;
        }
    }

    /**
     * Performs an preorder traversal on this binary tree by calling an
     * overloaded, recursive preorder method that starts with
     * the root.
     * 
     * @return an iterator over the binary tree
     */
    @Override
    public Iterator<T> iteratorPreOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        preOrder(0, tempList);

        return new TreeIterator(tempList.iterator());
    }


    protected void preOrder(int node, ArrayUnorderedList<T> tempList) 
    {
        if (node < tree.length)
            if (tree[node] != null) 
 	        { 
                tempList.addToRear(tree[node]);
                preOrder(node * 2 + 1, tempList);
                preOrder((node + 1) * 2, tempList);
            }
    }


    @Override
    public Iterator<T> iteratorPostOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        postOrder(0, tempList);

        return new TreeIterator(tempList.iterator());
    }


    protected void postOrder(int node, ArrayUnorderedList<T> tempList) 
    {
        if (node < tree.length)
            if (tree[node] != null) 
 	        {
                postOrder(node * 2 + 1, tempList); 
                postOrder((node + 1) * 2, tempList);
                tempList.addToRear(tree[node]);  
            }
    }


    @Override
    public Iterator<T> iteratorLevelOrder()
    {
        ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();
        int ct = 0;
        int i = 0;
        
        while (ct < count)
        {
            if (tree[i] != null)
            {
                tempList.addToRear(tree[i]);
                ct++;
            }
            i++;
        }
        
        return new TreeIterator(tempList.iterator());
    }
	

	private class TreeIterator implements Iterator<T>
	{
		private int expectedModCount;
		private Iterator<T> iter;
		

		public TreeIterator(Iterator<T> iter)
		{
			this.iter = iter;
			expectedModCount = modCount;
		}
		

		@Override
        public boolean hasNext() throws ConcurrentModificationException
		{
			if (!(modCount == expectedModCount))
				throw new ConcurrentModificationException();
				
			return (iter.hasNext());
		}
		

		@Override
        public T next() throws NoSuchElementException
		{
			if (hasNext())
				return (iter.next());
			else 
				throw new NoSuchElementException();
		}
		

		@Override
        public void remove()
		{
			throw new UnsupportedOperationException();
		}
	}
}

